#include <bits/stdc++.h>
#define ru(i,l,r) for(int i=(l);i<=(r);i++)
#define ru_(i,l,r) for(int i=(l);i<(r);i++)
#define rd(i,l,r) for(int i=(l);i>=(r);i--)
#define ll long long
#define pii pair<int,int>

using namespace std;

//数组移位模拟(取模循环); 枚举计数(max)实现dp；子数组枚举(O(n*log(n));  区间查询O(log(n));
class Solution {
public:
    vector<int> constructTransformedArray(vector<int>& nums) {
        vector<int> ans; int n=nums.size();
        ru_(i,0,n){
            int x=i, val=nums[i];
            if(val>0) x=(x+val)%n;
            else if(val<0) x=(x+n*10000+val)%n;
            else;
            ans.push_back(nums[x]);
        }; return ans;
    }
};
class Solution2 {
public:
    int maxRectangleArea(vector<vector<int>>& points) {
        int n=points.size(), ans=-1;
        ru_(i,0,n) ru_(j,i+1,n){
            int xa=min(points[i][0],points[j][0]), ya=min(points[i][1], points[j][1]);
            int xb=max(points[i][0],points[j][0]), yb=max(points[i][1], points[j][1]);
            auto check =[&](){
                int cnt=0;
                ru_(k,0,n){
                    if(points[k][0]<xa||points[k][0]>xb) continue;
                    if(points[k][1]<ya||points[k][1]>yb) continue;
                    if((points[k][0]==xa||points[k][0]==xb)&&(points[k][i]==ya||points[k][1]==yb)){cnt++; continue;}
                    return false;
                }; return cnt==4;
            };
            if (check()) ans=max(ans,(xb-xa)*(yb-ya));
        }; return ans;
    }
};

class Solution3 {
public:
    long long maxSubarraySum(vector<int>& nums, int K) {
        int n=nums.size();
        const ll INF=1E18; ll mn[K];
        ru_(i,0,K) mn[i]=INF;
        mn[K-1]=0;
        ll ans=-INF, sm=0;
        ru_(i,0,n){
            sm+=nums[i];
            ans=max(ans,sm-mn[i%K]);
            mn[i%K]=min(mn[i%K],sm);
        }; return ans;
    }
};

class Solution4 {
public:
    long long maxRectangleArea(vector<int>& xCoord, vector<int>& yCoord) {
        int n=xCoord.size(),m=0; map<int,int> mp;
        for(auto y: yCoord) mp[y]=1;
        for(auto &p:mp) p.second=++m;
        map<int, vector<pii>> vert;
        ru_(i,0,n) vert[xCoord[i]].push_back({mp[yCoord[i]],i});
        for(auto &p:vert) sort(p.second.begin(), p.second.end());

        int tree[m+1]; memset(tree,0,sizeof(tree));
        auto lb=[&](int x){return x&(-x);};
        auto add=[&](int pos){
            for(;pos<=m;pos+=lb(pos)) tree[pos]++;
        };
        auto query=[&](int pos){
            int ret=0;
            for(;pos>0;pos-=lb(pos))ret+=tree[pos];
            return ret;
        };
        ll ans=-1; map<pii,pii> last;
        for(auto &p:vert){
            auto &vec=p.second;
            ru_(i,0,vec.size()){
                add(vec[i].first);
                if(i>0){
                    pii key=pii(yCoord[vec[i-1].second], yCoord[vec[i].second]);
                    int cnt=query(vec[i].first)-query(vec[i-1].first-1);
                    if(last.count(key)){
                        pii val=last[key];
                        if(cnt-val.first==2){
                            int dx=p.first-val.second, dy=key.second-key.first;
                            ans=max(ans,1LL*dx*dy);
                        }
                    } last[key]={cnt,p.first};
                }
            }
        }
        return ans;
    }
};
int main(){
    Solution s;
    vector<int> nums={3,-2,1,1};
    for(auto x: s.constructTransformedArray(nums)) cout<<x<<" "; cout<<endl;

    Solution2 s2;
    vector<vector<int>> points = {{1,1},{1,3},{3,1},{3,3}};
    cout<<s2.maxRectangleArea(points)<<endl;

    Solution3 s3;
    vector<int> nums3={1,3}; int k=1;
    cout<<s3.maxSubarraySum(nums3, k)<<endl;

    Solution4 s4;
    vector<int> xCoord = {1,1,3,3}, yCoord = {1,3,1,3};
    cout<<s4.maxRectangleArea(xCoord, yCoord)<<endl;
}
